//
//  25.复杂链表复制.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/20.
//

import Foundation
/*
 题目：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
 思路1：用字典存储映射关系，空间换时间
 思路2：第⼀步：复制复杂指针的label和next。但是这次我们把复制的结点跟在元结点后⾯，⽽不是直接创建新的 链表； 第⼆步：设置复制出来的结点的random。因为新旧结点是前后对应关系，所以也是⼀步就能找到random； 第三步：拆分链表。奇数是原链表，偶数是复制的链表。
 */
func offer_25() {
    /*
     https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&tab=answerKey
     */
    print("测试用例查看剑指offer")
}

fileprivate class Solution {
    class RandomListNode: Hashable {
        func hash(into hasher: inout Hasher) {
            hasher.combine(self)
        }
        
        static func == (lhs: Solution.RandomListNode, rhs: Solution.RandomListNode) -> Bool {
            return lhs === rhs
        }
        
        var label: Int
        var next: RandomListNode? = nil
        var random: RandomListNode? = nil
        init(_ label: Int) {
            self.label = label
        }
    }
    
    func clone1(_ pHead: RandomListNode?) -> RandomListNode? {
        // write code here
        guard let pHead = pHead else { return nil }
        var dict = [RandomListNode: RandomListNode]()
        var p: RandomListNode? = pHead
        // 创建节点
        while p != nil {
            dict[p!] = RandomListNode(p!.label)
            p = p?.next
        }
        // 复制映射关系
        p = pHead
        while p != nil {
            dict[p!]?.next = p?.next == nil ? nil : dict[p!.next!]
            dict[p!]?.random = p?.random == nil ? nil : dict[p!.random!]
            p = p?.next
        }
        return dict[pHead]
    }
    
    func clone2(_ pHead: RandomListNode?) -> RandomListNode? {
        // write code here
        guard let pHead = pHead else { return nil }
        // 第⼀步：复制复杂指针的label和next，跟在原节点后面
        var p: RandomListNode? = pHead
        while p != nil {
            let pClone = RandomListNode(p!.label)
            pClone.next = p?.next
            p?.next = pClone
            p = pClone.next
        }
        // 第二步：处理random指针
        p = pHead
        while p != nil {
            let pClone = p?.next
            pClone?.random = p?.random?.next
            p = pClone?.next
        }
        // 第三步：拆分链表
        p = pHead
        let pCloneHead = p?.next
        var pCloneNode = pCloneHead
        p?.next = pCloneNode?.next
        while p != nil {
            pCloneNode?.next = p?.next
            pCloneNode = pCloneNode?.next
            p?.next = pCloneNode?.next
            p = p?.next
        }
        return pCloneHead
    }
}

